/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* buyNode(int x)
{
    Node* newnode=(Node*)malloc(sizeof(Node));
    newnode->val=x;
    newnode->next=newnode->random=NULL;

    return newnode;
}
//在原链表基础上复制
void Add(Node* phead)
{
     Node* pcur=phead;
     while(pcur)
     {
        Node* Next=pcur->next;
        //创建新节点，尾插到pcur
        Node* newnode=buyNode(pcur->val);
        pcur->next=newnode;
        newnode->next=Next;

        pcur=Next;
    }
}
struct Node* copyRandomList(struct Node* head) {
	if(head==NULL)
    {
        return NULL;
    }
    //原链表复制结点
    Add(head);
    //置random结点
    Node* pcur=head;
    while(pcur)
    {
        Node* copy=pcur->next;
        if(pcur->random!=NULL)
        {
            copy->random=pcur->random->next;
        }
        pcur=copy->next;
    }
    //断开链表
    pcur=head;
    Node* newHead,*newTail;
    newHead=newTail=pcur->next;
    while(pcur->next->next)
    {
        pcur=pcur->next->next;
        newTail->next=pcur->next;
        newTail=newTail->next;
    }
    return newHead;
}
